package com.hspedu.newData.dmsxl.滑动窗口;

import org.junit.Test;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-10 
 * @Version: 1.0
 */

public class LC239滑动窗口最大值 {

    // todo
    public int[] maxSlidingWindow1(int[] nums, int k) {

        int left = 0;
        int right = k;

        int i = 0;

        int max = -100000;
        int sum = 0;

        while (i<k){
            sum += nums[i++];
        }
        max = Math.max(max,sum);

        int res = 0;

        while (right < nums.length){

            sum += nums[right++];
            sum -= nums[left++];

            if (sum > max){
                max = sum;
                res = left;
            }
        }

        int[] result = new int[k];

        int j = 0;
        while (j<k){
            result[j++] = nums[res++];
        }
        return result;
    }


    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o1[0];
            }
        });
        int[] res = new int[len - k + 1];
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{nums[i],i});
        }

        res[0] = queue.peek()[0];
        for (int i = k ;i<len;i++){
            queue.offer(new int[]{nums[i],i});

            while (queue.peek()[1] <= i-k){
                queue.poll();
            }
            res[i-k+1] = queue.peek()[0];
        }

        return res;
    }

    @Test
    public void test() {
        // 测试代码

        int[] ints = maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        int[] ints1 = maxSlidingWindow(new int[]{1}, 1);
        System.out.println("=======");
    }

}
